TWiki > Book > WebHome (book view)	TWiki webs: Main | TWiki | Sandbox
	Book . { Home | Changes | Index | Search | Go }

This is the website for Strategies for Program Transformation, a book on program transformation with Stratego/XT. The book is currently in draft form. A future version might be published. New versions of chapters will be added over time.

For each chapter there is a separate wiki page that will be used to place additional material such as sample code, and which can also be used to post comments about the chapter.

[ Previous | Up | Next ]

Introduction

In the previous chapter we saw that pure term rewriting is not adequate for term rewriting because of the lack of control over the application of rules. Approaches for encoding such control within the pure rewriting paradigm lead to functionalized control by means of extra rules and constructors at the expense of traversal overhead and at the loss of the separation of rules and strategies. We need a mechanism that provides such control, but maintains the separation of rules and strategies and keeps traversal overhead to a minimum. Such a mechanism should allow strategies parameterized with selections from the available rules.

Also we saw that many transformation problems can be solved by alternative strategies such as a one-pass bottom-up or top-down traversal. Others can be solved by selecting the rules that are applied in an innermost normalization, rather than all the rules in a specification. However, no fixed set of such alternative strategies will be sufficient for dealing with all transformation problems. Rather than providing one or a few fixed rewriting strategies, we need to be able to compose strategies from basic building blocks with a few fundamental operators.

In program transformation, the basic building blocks are single rewrite steps, for example defined by a rewrite rule. This chapter introduces a set of operators for composing such single step transformations into complex transformations. By allowing abstraction over the basic transformation, generic transformation strategies can be defined. The combinators discussed in this chapter cover sequential programming and type-specific traversal. Extensions of this basic framework will be considered in later chapters.

Preprint

• Chapter-8.pdf
• Chapter-8.ps

Remarks

Lacks discussion of literature.

[ Previous | Up | Next ]

Introduction

So far we have assumed the basic actions applied by strategies are rewrite rules. However, taking a closer look at rules, we see that they are actually composed from several ingredients, i.e., matching the pattern in the left-hand side, verifying the side conditions, and instantiating the pattern on the right-hand side. In addition, a rule implicitly delimits the scope of the variables that it uses. If we take rules apart and make their components available as first-class strategy actions, many interesting idioms can be expressed directly.

This chapter introduces the strategy actions match (?p), build (p), and scope ({x1,...,xn:s}), and shows how unconditional and conditional rewrite rules can be expressed in terms of these actions. Many other language constructs that involve matching can also be expressed in terms of these operations.

Preprint

• Chapter-9.pdf
• Chapter-9.ps

Remarks

• Rule for explicit pattern matching is missing
• Rule for term project should use where

[ Previous | Up | Next ]

Introduction

In the previous chapters we saw how strategies can be used to control transformations and how rules can be broken down into the primitive actions match, build and scope. Together, these combinators allow us to define any transformation. However, the definition of traversals using congruence operators is specific for a data-type. Although a one step traversal can be factored out of the definition of full tree traversals, there are no generic definitions of traversals. This entails, that traversals should be defined for each data type.

In this chapter we introduce combinators for generic term traversal, that support data type independent definition of traversals, which can be reused for any data type. Furthermore, the strategies that we have inspected so far are geared to transform terms while preserving types, i.e., rephrasings according to the taxonomy in Chapter Program Transformation. There is also a class of transformations, in which terms are translated to a different type. In this chapter we introduce a generic term construction and decomposition operator, which allows us to define generic translation or type unifying strategies.

Preprint

• Chapter-10.pdf
• Chapter-10.ps

Remarks

Very draft

[ Previous | Up | Next ]

Introduction

Rewrite rules provide a good formalism for the formalization of transformation steps. However, term rewriting based on exhaustive normalization of a subject term with respect to the entire set of rewrite rules turns out not to be adequate for program transformation. In this chapter the problems associated with term rewriting are explored, and several proposed solutions are examined.

Preprint

• Chapter-7.pdf

[ Previous | Up | Next ]

Introduction

Program transformation systems need some kind of representation for program that can be manipulated. Programmers write programs as texts using text editors. Some programming environments provide more graphical (visual) interfaces for programmers to specify certain domain-specific ingredients (e.g., user interface components). But ultimately, such environments have a textual interface for specifying the details. Even if programs are written in a `structured format' such as XML, the representation used by programmers generally is text. So a program transformation system needs to manipulate programs in text format.

However, for all but the most trivial transformations, a structured rather than a textual representation is needed. To bridge the gap between textual and structured representation, parsers and unparsers are needed. Since the theory of formal languages, context-free and regular grammars, and parser construction are standard fair, we will not treat those subjects here. The purpose of this chapter is to introduce the terminology and formalisms used in the rest of this book. This includes formal syntax definition with the syntax definition formalism SDF, parsing, representation of trees as ATerms, mapping of parse trees to abstract syntax trees, and pretty-printing using the target-independent Box language. We illustrate these concepts with a syntax definition for a subset of the Tiger language used in the rest of this book.

Preprint

• Chapter-4.pdf
• Chapter-4.ps

Abstract

Many systems for program transformation exist that are often specialized for a specific object language and/or kind of transformation. All these systems share many ideas about program transformation and use similar techniques, but are often ad-hoc in many respects. The ultimate goal is to achieve a specification language or family of specification languages for the high-level, declarative specification of program transformation systems in which generic, language independent schemas of transformation can be captured, and which admits efficient implementation of those transformations that can scale up to large programs.

This book describes one contribution towards this goal, the Stratego/XT language and toolset for the construction of program transformation systems. In this chapter the requirements and design space for transformation systems are explored.

Preprint

• Chapter-1.pdf
• Chapter-1.ps

Abstract

Many systems for program transformation exist that are often specialized for a specific object language and/or kind of transformation. All these systems share many ideas about program transformation and use similar techniques, but are often ad-hoc in many respects. The ultimate goal is to achieve a specification language or family of specification languages for the high-level, declarative specification of program transformation systems in which generic, language independent schemas of transformation can be captured, and which admits efficient implementation of those transformations that can scale up to large programs.

This book describes one contribution towards this goal, the Stratego/XT language and toolset for the construction of program transformation systems. In this chapter the requirements and design space for transformation systems are explored.

Preprint

• Chapter-2.pdf
• Chapter-2.ps

[ Previous | Up | Next ]

Introduction

Meta-programs manipulate structured representations (abstract syntax) of programs. The distance between the concrete syntax meta-programmers use to reason about programs and the notation for abstract syntax manipulation provided by general purpose (meta-) programming languages is too large for many applications. In this chapter it is shown how the syntax definition formalism SDF can be employed to fit a meta-programming language with concrete syntax notation for composing and analyzing object programs. As a case study, the addition of concrete syntax to the program transformation language Stratego is presented. The approach is then generalized to arbitrary meta-languages.

Preprint

• Chapter-6.pdf
• Chapter-6.ps

[ Previous | Up ]

Introduction

The applicability of term rewriting to program transformation is limited by the lack of control over rule application and by the context-free nature of rewrite rules. The first problem is addressed by user-definable rewriting strategies. This chapter addresses the second problem by extending rewriting strategies with scoped dynamic rewrite rules. Dynamic rules are generated at run-time and can access variables available from their definition context. Rules generated within a rule scope are automatically retracted at the end of that scope. The technique is illustrated by means of several program tranformations: bound variable renaming, function inlining, and dead function elimination.

Preprint

• Chapter-11.pdf
• Chapter-11.ps

See Part I

[ Previous | Up | Next ]

Introduction

In the previous chapter we saw how terms provide a structured representation for programs derived from a formal definition of the syntax of the programming language. Transforming programs then requires tranformation of terms. There are various ways such transformations could be defined. In this chapter we consider the paradigm of term rewriting for specifying program transformations. In term rewriting a term is transformed by repeated application of rewrite rules. In the first section we first examine the equivalence of expressions and equational reasoning. Then we will formally define term patterns, substitution, term pattern matching, rewrite rules, and normalization with respect to a set of rewrite rules.

Preprint

• Chapter-5.pdf
• Chapter-5.ps

For announcements of new version, questions and remarks about chapters, subscribe to the following mailinglist:

• https://mail.cs.uu.nl/mailman/listinfo/stratego-book

Introduction

[ Previous | Up | Next ]

Contents

• Chapter Program Transformation
• Chapter Program Transformation Systems
• Chapter Strategies for Program Transformation A Roadmap

Introduction

This introductory part provides a global overview of the field of program transformation. Chapter Program Transformation introduces a taxonomy of applications of program transformation illustrated with many example transformations. Chapter Program Transformation Systems discusses the requirements for and issues in the realization of program transformation systems. Chapter Roadmap provides a roadmap for the rest of the book.

Preprint

• Part-I.pdf

Program Transformation by Term Rewriting

• Chapter Program Representation
• Chapter Term Rewriting
• Chapter Program Transformation with Concrete Object Syntax

Programmable Rewriting Strategies

Contents

• Chapter In Control of Rewriting
• Chapter Composing Strategies
• Chapter First Class Pattern Matching
• Chapter Generic Traversal Strategies
• Chapter Scoped Dynamic Rewrite Rules

Introduction

Rewrite rules provide a good formalism for expressing basic program transformation steps. However, rewriting has a number of limitations. First, since most sets of rules are not confluent and/or terminating, exhaustive application of rules is not adequate; more careful control over the application of rewrite rules is needed.

Chapter In Control of Rewriting surveys several solutions to controlling rewriting. Most solutions for the encoding of control suffer from a substantial overhead in the definition of traversals and/or intertwine transformation rules and strategy. The paradigm of programmable rewriting strategies provides a solution with minimal overhead for traversal, while maintaining the separation of rules and strategies.

Chapter Composing Strategies to Chapter Generic Traversal Strategies introduce combinators for the composition of programmable strategies. Chapter Composing Strategies introduces combinators for sequential non-deterministic programming and for data type specific traversal using congruence operators. Chapter First Class Pattern Matching reduces rewrite rules to the more primitive strategy actions match, build, and scope. The availability of first class patterns allows many other operations involving pattern matching. Data type specific traversal with congruence operators does solve the separation between rules and strategies, but not the overhead caused by the specification of traversals. Chapter Generic Traversal Strategies shows how combinators for generic traversal can concisely capture traversal schemata independent of any object language.

Another limitation of rewriting is that rewrite rules are context-free. That is, only local information available during the pattern match can be used in a transformation step. In Chapter Scoped Dynamic Rewrite Rules the paradigm of rewriting strategies is extended with scoped dynamic rewrite rules, rules which are generated at run-time to inherit context information.

Web	TWiki Site Map	Use to...
Main	The Main web is dedicated to the maintenance of this website. This is the place to discuss meta-issues such as what style to use, how best to organize a survey, what the ideal topic size is, how to refer to papers, what the preferred layout of the site should be, etc.	...
TWiki	Welcome, Registration, and other StartingPoints; TWiki history & Wiki style; All the docs...	...discover TWiki details, and how to start your own site.
Gmt	Generative Model Transformer
Gpce
Octave	The Stratego web is the home of Stratego, a language for program transformation based on the paradigm of rewriting strategies. The aim of this language is to provide an expressive and declarative language for expressing all kinds of program transformations. The web includes publications on Stratego, download of the StrategoCompiler, documentation, and descriptions of applications.	...
Sandbox	Sandbox test area with all features enabled.	...experiment in an unrestricted hands-on web.
Sdf	The Sdf web is dedicated to the modular syntax definition formalism SDF. Here you can find implementations, pointers to download pages, syntax definitions for common languages, discussions about new features and implementatios of SDF, and tips and tricks for using the formalism.	...
SdfBackup	The Sdf web is dedicated to the modular syntax definition formalism SDF. Here you can find implementations, pointers to download pages, syntax definitions for common languages, discussions about new features and implementatios of SDF, and tips and tricks for using the formalism.	...
Stratego	The Stratego web is the home of Stratego, a language for program transformation based on the paradigm of rewriting strategies. The aim of this language is to provide an expressive and declarative language for expressing all kinds of program transformations. The web includes publications on Stratego, download of the StrategoCompiler, documentation, and descriptions of applications.	...
Sts	The Sofware Transformation Systems wiki
Tiger	Home of the Tiger in Stratego project, which is concerned with the exploration of transformation techniques in compilation using an implementation of a Tiger compiler.	...
Tools	The Tools web is the home of the XT? bundle of program transformation tools. XT is an open framework for program transformation based on the ATerm format for exchange of programs between tools. The bundle includes packages for parsing, pretty-printing, term rewriting, and grammar recovery. It also contains a distribution of the SDF2? GrammarBase?. The OnlinePackageBase is an open collection of packages for program transformation supporting package bundling on demand.	...
Transform	The Transform web is an attempt to get an overview of program transformation research and application. In the first place the web is a collection of resources such as pointers to researchers, conferences, journals, summaries and reviews of papers, and tools for implementing transformation systems. In the second place the Transform web attempts to bring structure in the world of program transformation by means of categories, taxonomies such as the TransformationTaxonomy, and entry points such as the ReengineeringWiki and the DeCompilation page.	...
You can use color coding by web for identification and reference. This table is updated automatically based on WebPreferences settings of the individual webs. Contact webmaster@strategoxt.org if you need a separate collaboration web for your team. See also AdminTools.

Legend of icons:

= Go to the home of the web = Search the web

= See recent changes in the web = Subscribe to get notified of changes by e-mail

Part I Introduction

• Chapter Program Transformation
• Chapter Program Transformation Systems
• Chapter Strategies for Program Transformation A Roadmap

Part II Program Transformation by Term Rewriting

• Chapter Program Representation
• Chapter Term Rewriting
• Chapter Program Transformation with Concrete Object Syntax

Part III Programmable Rewriting Strategies

• Chapter In Control of Rewriting
• Chapter Composing Strategies
• Chapter First Class Pattern Matching
• Chapter Generic Traversal Strategies
• Chapter Scoped Dynamic Rewrite Rules

Strategies for Program Transformation

An Introduction to Program Transformation with Stratego/XT

Stratego/XT

Eelco Visser

DRAFT

2003

The complete draft book is now available as a single PDF file.

We have also started developing an online manual. See the strategoxt-manual project at http://www.stratego-language.org/release

• Cover
• About this book
• Table of Contents
• News
• MailingList

Copying and Citing

copyright © 2003,2004 Eelco Visser

The book chapters that are published here are intended to provide an overview of the main ideas behind the Stratego language and XT toolset. Since the current version is a draft, it should not be considered as the definitive source about Stratego/XT.

The copyright is with the author, Eelco Visser. The book chapters password protected and are available on request (visser+book@cs.uu.nl). Re-distribution of material published here is not allowed. When referring to the website use the following URL:

• http://www.stratego-language.org/Book

When referring to Stratego/XT in publications, please refer to the relevant published papers. Good general references are 'Building Program Optimizers with Rewriting Strategies' and 'Program Transformation with StrategoXT'.

When citing the book in a publication use the following BibTeX entry:

@Book{SPT,
  author = {Eelco Visser},
  title = {Strategies for Program Transformation.
           {An} Introduction to Program Transformation 
           with Stratego/XT},
  year = 2003,
  note = {http://www.stratego-language.org/Book},
  url = {http://www.stratego-language.org/Book}
}

News

2003-12-14

Chapter 11: Scoped Dynamic Rewrite Rules

2003-12-10

Chapter 10: Generic Traversal Strategies

2003-12-08

Chapter 9: First Class Pattern Matching

2003-12-03

Chapter 8: Composing Strategies

2003-12-01

Chapter 7: In Control of Rewriting

2003-11-25

Chapter 6: Program Transformation with Concrete Object Syntax

Chapter 5: Term Rewriting

2003-11-19

Chapter 4: Program Representation

2003-11-17

Chapters 1 - 3: Introduction

2003-11-16

Creation of a website for the Stratego book.

See also

• WebChanges100
• WebChanges200
• WebChanges500

• AboutThisBook
• ChapterComposingStrategies
• ChapterFirstClassPatternMatching
• ChapterGenericTraversalStrategies
• ChapterInControlOfRewriting
• ChapterProgramRepresentation
• ChapterProgramTransformation
• ChapterProgramTransformationSystems
• ChapterProgramTransformationWithConcreteObjectSyntax
• ChapterScopedDynamicRewriteRules
• ChapterStrategiesForProgramTransformationARoadmap
• ChapterTermRewriting
• MailingList
• PartI
• PartII
• PartIII
• SiteMap
• TableOfContents
• TitlePage
• TitlePageInContents
• UpdateWebPages
• WebChanges
• WebChanges100
• WebChanges200
• WebChanges500
• WebCustomMenus
• WebHome
• WebIndex
• WebLeftBar
• WebNews
• WebNewsInBar
• WebNotify
• WebPreferences
• WebSearch
• WebStatistics
• WebTools

Part I

Part II

Part III

2003-12-14

Chapter 11: Scoped Dynamic Rewrite Rules

2003-12-10

Chapter 10: Generic Traversal Strategies

2003-12-08

Chapter 9: First Class Pattern Matching

2003-12-03

Chapter 8: Composing Strategies

2003-12-01

Chapter 7: In Control of Rewriting

2003-11-25

Chapter 6: Program Transformation with Concrete Object Syntax

Chapter 5: Term Rewriting

2003-11-19

Chapter 4: Program Representation

2003-11-17

Chapters 1 - 3: Introduction

2003-11-16

Creation of a website for the Stratego book.

News

2003-12-14

Chapter 11: Scoped Dynamic Rewrite Rules

2003-12-10

Chapter 10: Generic Traversal Strategies

2003-12-08

Chapter 9: First Class Pattern Matching

2003-12-03

Chapter 8: Composing Strategies

2003-12-01

Chapter 7: In Control of Rewriting

2003-11-25

Chapter 6: Program Transformation with Concrete Object Syntax

Chapter 5: Term Rewriting

2003-11-19

Chapter 4: Program Representation

2003-11-17

Chapters 1 - 3: Introduction

2003-11-16

Creation of a website for the Stratego book.

WebNotify is a subscription service to be automatically notified by email when topics change in the TWiki.Book web. This is a convenient service, so you do not have to come back and check all the time if something has changed. To subscribe to the service, please put yourself on the list below. The format is: 3 spaces * Main.yourWikiName - yourEmailAddress

• EelcoVisser - visser@cs.uu.nl

Note: It is helpful to insert your name in alphabetical order (by first name -- ignore the "Main.") -- then you can find your name (or not) more easily if you wish to remove it or confirm that you are on the list.

Related topics: TWikiUsers, TWikiRegistration

TWiki.Book Web Preferences

The following settings are web preferences of the TWiki.Book web. These preferences overwrite the site-level preferences in TWikiPreferences, and can be overwritten by user preferences (your personal topic, i.e. TWikiGuest in the TWiki.Main web)

Preferences:

• • Set BOOKURL = http://www.cs.uu.nl/~visser/book

• • Set WEBTITLE = Strategies for Program Transformation

• • Set WEBLOGO = /pub/Stratego/StrategoLogo/StrategoLogoTextless-100px.png
  • Set WEBICON = /pub/StrategoLogoIcon.png

• List of topics of the TWiki.Book web:
  • Set WEBTOPICLIST = Home | Changes | Index | Search | Go

• Web specific background color: (Pick a lighter one of the StandardColors)
  • Set WEBBGCOLOR = #EEEEAA

• Exclude web from a web="all" search: (Set to on for hidden webs)
  • Set NOSEARCHALL =

• Default template for new topics and form(s) for this web:
  • WebTopicEditTemplate^?: Default template for new topics in this web. (Site-level is used if topic does not exist)
  • TWiki.WebTopicEditTemplate: Site-level default template
  • TWikiForms: How to enable form(s)
  • Set WEBFORMS =

• Users or groups who are not / are allowed to view / change / rename topics in the Book web: (See TWikiAccessControl)
  • Set DENYWEBVIEW =
  • Set ALLOWWEBVIEW =
  • Set DENYWEBCHANGE =
  • Set ALLOWWEBCHANGE =
  • Set DENYWEBRENAME =
  • Set ALLOWWEBRENAME =

• Users or groups allowed to change or rename this WebPreferences topic: (I.e. TWikiAdminGroup)
  • Set ALLOWTOPICCHANGE =
  • Set ALLOWTOPICRENAME =

• Web preferences that are not allowed to be overridden by user preferences:
  • Set FINALPREFERENCES = WEBTOPICLIST, DENYWEBVIEW, ALLOWWEBVIEW, DENYWEBCHANGE, ALLOWWEBCHANGE, DENYWEBRENAME, ALLOWWEBRENAME

Notes:

• A preference is defined as:
  6 spaces * Set NAME = value
  Example:
  • Set WEBBGCOLOR = #FFFFC0
• Preferences are used as TWikiVariables by enclosing the name in percent signs. Example:
  • When you write variable %WEBBGCOLOR% , it gets expanded to #EEEEAA .
• The sequential order of the preference settings is significant. Define preferences that use other preferences first, i.e. set WEBCOPYRIGHT before WIKIWEBMASTER since %WEBCOPYRIGHT% uses the %WIKIWEBMASTER% variable.
• You can introduce new preferences variables and use them in your topics and templates. There is no need to change the TWiki engine (Perl scripts).

Related Topics:

• TWikiPreferences has site-level preferences.
• TWikiUsers has a list of user topics. User topics can have optional user preferences.
• TWikiVariables has a list of common %VARIABLES%.
• TWikiAccessControl explains how to restrict access by users or groups.

Number of topics: 0

• Topic index: List of Book topics in alphabetical order.
  |All|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|
  | All topics in BookView |

• Jump to topic: If you already know the name of the topic, enter the name of the topic into the GoBox at the top

• WebChanges: Find out what topics in Book have changed recently

• How to edit text:
  • Make changes to topics in GoodStyle,
  • Learn the TextFormattingRules, and
  • Have a look at the TextFormattingFAQ

Statistics for TWiki.Book Web

Notes:

• Do not edit this topic, it is updated automatically. (You can also force an update)
• TWikiDocumentation tells you how to enable the automatic updates of the statistics.
• Suggestion: You could archive this topic once a year and delete the previous year's statistics from the table.

Finding topics

• RoadMap^?
• WebIndex: all topics in the Book web
• WebSearch: find topics

Tracking activity

• WebNews: selected changes
• WebChanges: recent changes
• WebNotify: email notification of changes
• WebStatistics: usage counts

Look and feel

• WebPreferences: values of variables
• WebContents^?: web specific entries in the side bar

Number of topics: 36